package list;

import javax.xml.soap.Node;
import java.util.Stack;

/**
 * @version 1.0
 * 功能目的描述 ：用于   单链表的模拟  水浒英雄 ========>>>>>>>>>>>
 * @author： pang-yun
 * @date： 2021-07-15 19:45
 */
public class SingleLinkedListDemo {

    public static void main(String[] args) {
        //进行测试 先进行节点的创建
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        // 未按编号 加入
     /*   singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);

        singleLinkedList.list();*/

        //  按编号加入
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

      /*  singleLinkedList.list();
        System.out.println("----------getLength-------");
        System.out.println(SingleLinkedList.getLength(singleLinkedList.getHead()));

*/
    /*    System.out.println("update---2--------------");
        HeroNode heroUpdateBy2 = new HeroNode(2, "庞云", "最后的圣光");
        singleLinkedList.update(heroUpdateBy2);
        singleLinkedList.list();*/


      /*  System.out.println("-----------delete----------------");
        singleLinkedList.delete(hero4);
        singleLinkedList.list();*/


    /*    System.out.println("----------------index reverse------------");
        HeroNode indexNode = SingleLinkedList.findIndexNode(singleLinkedList.getHead(), 1);
        System.out.println(indexNode.toString());*/


        singleLinkedList.list();
        System.out.println("----------reverseList------------------");
        SingleLinkedList.reverse(singleLinkedList.getHead());
        singleLinkedList.list();

        System.out.println("---------reversePrint-----------");

        SingleLinkedList.reversePrint(singleLinkedList.getHead());


    }
}


//定义HeroNode  ， 每个HeroNode 对象就是一个节点
class HeroNode {
    public Integer number;
    public String name;
    public String nickName;
    public HeroNode next;  //指向下一个节点

    //构造器
    public HeroNode(Integer number, String name, String nickName) {
        this.number = number;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode [ number = " + number + ",name = " + name + " , nickName = " + nickName + "]";
    }
}

//开始创建单链表
class SingleLinkedList {
    //先初始化一个头结点， 头结点不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    //添加节点到单项列表
    //思路： 找到当前链表的最后节点  然后将最后节点的next 指向 新的节点
    public void add(HeroNode heroNode) {

        //头结点 不能动， 我们需要自定义一个节点  temp 来遍历链表
        HeroNode temp = head;

        //遍历链表  找到最后
        while (true) {
            if (temp.next == null) {
                break;
            }
            //如果不是，则将temp后移
            temp = temp.next;
        }
        //最后找到 链表尾部  将next指向 新的节点
        temp.next = heroNode;
    }

    //第二种 添加方式 根据排名将英雄插入到指定位置
    public void addByOrder(HeroNode heroNode) {
        //头结点不能动，我们仍需要通过一个辅助变量来找到添加的位置
        // 单链表，我们找到的 应该是 插入的前一个位置  否则heroNode 中的 next 无法插入
        HeroNode temp = head;
        boolean flag = false;  // 标识  用于查看 是否有这个排名英雄

        //插入的几种情况实现
        while (true) {
            if (temp.next == null) {   //说明temp已经在链表的最后
                break;
            }

            if (temp.next.number > heroNode.number) {  //下一个的number > 插入的num   说明已经找到了相关的位置
                break;
            }

            if (temp.next.number == heroNode.number) {  //已经有 number 相同的英雄存在
                flag = true;
                break;
            }

            temp = temp.next;  // 没有遇到相关的时  指针后移
        }

        //先通过flag判断 是否能插入
        if (flag) {//已经存在·  不能添加
            System.out.printf("要添加的英雄%d已经存在，不能插入", heroNode.number);
        } else {
            // 插入到链表中   temp后面
            heroNode.next = temp.next;     // 将 指向下一个位置的 换成  新插入的
            temp.next = heroNode;         // 将在temp后面插入  所以temp.next  = heroNode

        }
    }


    //修改节点信息   注意： number 不能修改  否则相当于添加

    public void update(HeroNode heroNode) {
        //判断 list 是否为空
        if (head.next == null) {
            System.out.println("list为空");
            return;
        }

        //需要根绝number找到要修改的节点  和以前一样   需要辅助变量  以及标志flag
        HeroNode temp = head;  //临时变量
        boolean flag = false;   // 是否找到节点的标志
        while (true) {
            if (temp.next == null) {
                break;   //已经遍历了
            }

            if (temp.number == heroNode.number) {
                flag = true;
                break;
            }
            temp = temp.next;  //未找到  后移
        }


        //根据 flag 来判断是否找到
        if (flag) {
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
        } else {
            System.out.printf("未找到要修改的%d", heroNode.number);
        }
    }

    //删除节点
    public void delete(HeroNode heroNode) {
        //判断list是否为空
        if (head.next == null) {
            System.out.println("list为空");
            return;
        }

        HeroNode temp = head;
        boolean flag = false;

        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.number == heroNode.number) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.printf("未找到%d\n", heroNode.number);
        }
    }


    //遍历链表
    public void list() {
        //判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        //采用辅助变量来遍历单链表
        HeroNode temp = head.next;
        while (true) {
            //判断链表是否已经到最后
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);

            //将temp后移
            temp = temp.next;
        }
    }

    //过去单链表节点个数
    public static int getLength(HeroNode head) {
        if (head.next == null) {
            System.out.println("此单链表为空！！");
            return 0;
        }
        int length = 0;
        HeroNode temp = head;
        while (temp.next != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }


    //查找单链表的倒数第k个节点
    /*
     * 1.接收head节点，同时接收index
     * 2.index代表倒数第几个节点
     * 3.利用getLength得到链表长度
     * 4.然后从头开始遍历  将 temp 指向 （length -index）
     *
     * */
    public static HeroNode findIndexNode(HeroNode head, int index) {
        //检验是否为空
        if (head.next == null) {
            System.out.println("list为空");
            return null;
        }
        int length = getLength(head);

        //检验 index 是否合法
        if (index <= 0 || index > length) {
            System.out.println("已经超出范围");
            return null;
        }
        HeroNode temp = head;
        // 利用for 找到 目标
        for (int i = 0; i <= length - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    //单链表的反转
    /*
     * 思路： 新建一个头结点  newHead  将原链表上的取下来 放到新建newNode后面
     *    将 current 的next 连接  newNode 的next
     *       将newNode头结点 连接 current
     *       指针下移
     *   重复这个循环
     * */
    public static void reverse(HeroNode head) {
        //如果当前链表为空  或者只有一个节点时  可以直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }

        //用于定位 节点 并将该节点移动到 reverseNode后面
        HeroNode current = head.next;

        //另一个定位指针，  current移走后   利用这个指针 找原链表
        HeroNode currentNext = null;

        //新建一个头节点
        HeroNode newHead = new HeroNode(0, "", "");

        while (current!= null) {
            //1. current的next 连接 newNode原有的next    newNode 的next 连接 current  相当于 中间插入了 current
            currentNext = current.next;
            current.next = newHead.next;
            newHead.next = current;
            // 2. 将 current 后移一位  对下一个节点进行反转
            current=currentNext;
        }
        // 将 newHead头结点  换成  head  即将反转后的链表 接在 head 上  完成
        head.next = newHead.next;

    }

    //利用栈 从尾到头 遍历 单链表
    public static void reversePrint(HeroNode head){
        //检验是否为空
        if (head.next==null){
            System.out.println("此链表为空!");
            return;
        }

        //建立栈
        Stack<HeroNode> stack = new Stack<>();

        HeroNode current =head.next;
        //将链表的node 压入栈中
        while (current!=null){
            stack.push(current);
            current=current.next;
        }

        //从栈中取出 打印
        while (stack.size()>0){
            System.out.println(stack.pop());
        }
    }


}

